package org.everyday;

import cn.hutool.core.lang.Pair;
import com.common.TreeNode;

import java.util.*;

/**
 * @Author: Tang World
 * @Date: 5/9/2022 上午10:21
 */
public class L652 {
    HashMap<String, TreeNode> seen = new HashMap<>();
    HashSet<TreeNode> repeat = new HashSet<>();
    HashMap<String, Pair<TreeNode, Integer>> seen2 = new HashMap<>();
    int index = 0;

    public static void main(String[] args) {
        TreeNode root = TreeNode.buildTree(new Integer[]{2, 2, 2, 3, null, 3, null});
        List<TreeNode> duplicateSubtrees = new L652().findDuplicateSubtrees(root);
        duplicateSubtrees.forEach(p -> System.out.println(p.val));
    }

    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        dfs2(root);
        return new ArrayList<>(repeat);
    }

    private String dfs(TreeNode root) {
        if (root == null) {
            return "";
        }
        StringBuilder sb = new StringBuilder();
        sb.append(root.val);
        sb.append("(");
        sb.append(dfs(root.left));
        sb.append(")(");
        sb.append(dfs(root.right));
        sb.append(")");
        String serial = sb.toString();
        if (seen.containsKey(serial)) {
            repeat.add(seen.get(serial));
        } else {
            seen.put(serial, root);
        }
        return serial;
    }

    private int dfs2(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // 仅当三元组完全相同时，才是相同子树
        int[] tr = new int[]{root.val, dfs2(root.left), dfs2(root.right)};
        String hash = Arrays.toString(tr);
        if (seen2.containsKey(hash)) {
            Pair<TreeNode, Integer> pair = seen2.get(hash);
            repeat.add(root);
            return pair.getValue();
        } else {
            seen2.put(hash, new Pair<>(root, ++index));
            return index;
        }
    }
}
